As an increasing number of applications and services are being made available over networks such as the Internet, an increasing number of content, application, and/or service providers are turning to technologies such as cloud computing. Cloud computing, in general, is an approach to providing access to electronic resources through services, such as Web services, where the hardware and/or software used to support those services is dynamically scalable to meet the needs of the services at any given time. A user or customer typically will rent, lease, or otherwise pay for access to resources through the cloud, and thus does not have to purchase and maintain the hardware and/or software needed. As such, the applications and services of a user are often hosted on the host servers of a service provider or other operator of the environment. In such a scenario, it can be important for the service provider or other operator to provide protection against various power failures, network outages and other unexpected events that may occur in order to ensure that the user's services continue to run reliably and uninterrupted. One particular issue that may arise is the ability to quickly and securely recover hosts in the event of large scale events, such as widespread network faults and/or power failures.